/**
 * @version: V1.0
 * @Title: Test06_AddTwoNumbers.java
 * @Description:
 * @author wangshipeng
 * @date 2022-01-17 22:19
 * @Copyright: 2022-01-17
 */

package com.peng.linkedlist;

/**
 * @author wangshipeng
 * @ClassName: Test06_AddTwoNumbers
 * @Description: 给定两个链表的头节点head1和head2，
 * 认为从左到右是某个数字从低位到高位，返回相加之后的链表
 * 例子     4 -> 3 -> 6        2 -> 5 -> 3
 * 返回     6 -> 8 -> 9
 * 解释     634 + 352 = 986
 * @date 2022-01-17 22:19
 */
public class Test06_AddTwoNumbers {

    public static Node addTwoNumbers(Node head1, Node head2) {

        int l1Length = length(head1);
        int l2Length = length(head2);

        Node longNode = l1Length > l2Length ? head1 : head2;
        Node shortNode = longNode == head1 ? head2 : head1;
        Node res = longNode;

        int carry = 0;
        int val = 0;
        Node last = longNode;
        while (shortNode != null) {
            val = shortNode.value + longNode.value + carry;
            longNode.value = val % 10;
            carry = val / 10;
            last = longNode;
            longNode = longNode.next;
            shortNode = shortNode.next;
        }

        while (longNode != null) {
            val = longNode.value + carry;
            longNode.value = val % 10;
            carry = val / 10;
            last = longNode;
            longNode = longNode.next;
        }

        if (carry != 0) {
            last.next = new Node(1);
        }

        return res;

    }

    public static int length(Node head) {
        int length = 0;
        while (head != null) {
            head = head.next;
            length++;
        }
        return length;
    }

    public static void main(String[] args) {
        Node head1 = LinkedListUtils.link(
                new Node(3),
                new Node(2),
                new Node(9)
        );
        Node head2 = LinkedListUtils.link(
                new Node(1),
                new Node(2),
                new Node(3)

        );
        Node result = addTwoNumbers(head1, head2);
        LinkedListUtils.printNodes(result);
    }
}
